As processors have become faster, main memory access has become the bottleneck to overall increased system performance. Therefore, in order to improve performance, memory caching schemes have been adopted to lessen the effect of the main memory bottleneck. The PENTIUM processor employs one such memory caching scheme. In accordance with the PENTIUM processor's caching scheme, when the processor needs to read data from memory, the processor first checks the primary cache to locate the data. If the data is located in the primary cache, the data is returned to the processor. If the requested data is not located in the primary cache, then the secondary cache is checked, which has a slower access time than the primary cache, but is still much faster than main memory. If the data is located in the secondary cache, the data is returned to the processor and the line ("cache line") of the secondary cache that stored the data is copied into the primary cache. That is, rather than just copying the data that is being read to the primary cache, an entire 32-byte cache line is copied to the primary cache. The primary cache is 8 KB in size, so it can store 256 cache lines. The secondary cache is typically 64 KB to 512 KB, so it can store between 2,048 to 16,384 cache lines.
If after checking the secondary cache the data is still not located, main memory is accessed, which has a significantly slower access time than the secondary cache. When main memory is accessed, not only the requested data, but an entire memory line of 32 bytes is returned. Upon returning the 32 bytes, the processor receives the data it requested and the primary and secondary cache both receive the entire 32-byte memory line, also known as a cache line. The 32-byte memory line is stored in the primary cache in the hope that the next time the processor needs to read data from memory, the data will be found within this cache line, saving a main memory access which saves significant processing time. To put the costs in perspective, it takes 1 processor cycle to access the primary cache, 4-12 processor cycles to access the secondary cache, and 50 processor cycles to access main memory. Therefore, the primary cache could be searched perhaps 50 times in the time that it takes to access main memory once. The PENTIUM processor's caching mechanism is described in greater detail in Anderson and Shanley, Pentium Processor System Architecture, 2d ed., Addison-Wesley, 1995, pp. 35-60, which is hereby incorporated by reference.
Object loaders have been developed that load objects into memory in response to an application program's request to use the object. One example of an object is a portion of data, such as a range of spreadsheet cells from a spreadsheet program. In some conventional systems, when an application program wants to use an object, it has an identifier of the object, but it must obtain the memory address of the object before the object can be utilized. In this situation, an object loader is utilized to obtain the memory address. If, however, the object is not already loaded into memory, the object loader locates the object from a secondary storage device, stores the object into memory, and returns the memory address.
Some conventional object loaders use a conventional hashing mechanism to assist in performing their functionality. Conventional hashing mechanisms utilize a data structure known as a hash table to provide direct access to stored data. One example of a conventional hashing mechanism 100 is depicted in FIG. 1. The hashing mechanism 100 comprises a key 102, a hash function 104, a hash index 106, and a hash table 108. The hash table 108 contains a number of hash buckets 110-130, and each hash bucket contains data, such as a record, with one of the fields of the record acting as the key 102. In order to access the hash table 108, the key 102 is input into a hash function 104 which yields an index 106 (or hash address) that refers to a specific hash bucket (e.g., 114). Within the hash bucket 114 is the data that matches the key, unless the data has not yet been stored in the hash bucket. Hash tables are useful because they provide direct access to data by mapping a large range of key values into a smaller range of indexes. In this manner, for example, if a key of eight digits were utilized having a range of key values from 0 to 99,999,999 and if less than ten values are ever used, a hashing mechanism can be used to hash the key into an index of one digit to refer to a hash table containing ten buckets. Therefore, instead of using a hash table having one-hundred-million hash buckets where only a very limited number of the buckets are ever used, a hash table of only ten buckets can be used to more efficiently use system resources, but still provide direct access to the data.
The function "h" 104 maps each key value onto exactly one index, and therefore, whenever the same key value is used more than once, the same index 106 into the hash table 108 is generated. Sometimes, however, when attempting to store data in the hash table 108, more than one key value will hash to the same index 106. In this situation, a "collision" has occurred. When a collision occurs, the data must be stored in the hash bucket indicated by the index and therefore more than one record will be stored in this hash bucket. Hash bucket 118 depicts the state of a hash bucket after a collision has occurred and more than one record is stored in the hash bucket. In hash bucket 118, one record of data "data 3" is linked to a second record of data "data 4." As more collisions occur, the hash buckets become more populated and thus the benefits of a hash table start to diminish because each record within the hash bucket is no longer directly accessible. Instead, after hashing the key value into an index, the index refers to a hash bucket that contains a number of records linked together and the hash bucket must then be searched to determine the correct record, which is costly in terms of processing time. Therefore, conventional hashing systems are designed to avoid collisions.
The conventional object loaders utilize the conventional hashing mechanism 100 by using an object identifier as the key 102 and by storing both the memory addresses of the objects and the object identifiers as the data in the hash buckets 110-130 of the hash table 108. As such, upon receiving an object identifier of a given object from an application program, the conventional object loader retrieves the memory address of the object by applying the hash function 104 to the object identifier to create an index 106 which refers to a hash bucket of the hash table 108 and by retrieving the memory address for the object from the hash bucket. If the memory address for the object is not yet contained in the hash table, the object loader locates the object from a secondary storage device, stores the object into memory, stores the memory address into the hash table, and returns the memory address.
The processing of conventional object loaders can take a significant amount of processing time to locate objects and to load them into memory. This processing becomes even more burdensome on the system as the number of objects utilized within the system becomes extremely large. In addition, a significant amount of processing time and memory is used to locate an object even after loading it into memory. Thus, it is desirable to improve the performance of object loaders. However, conventional object loaders have not taken advantage of the caching architecture of today's processors to improve performance.